/**
 * Dijkstra 单源最短路径算法
*/

#include "MGraph.c"

#ifndef MGRAPH_DIJKSTRA
#define MGRAPH_DIJKSTRA

// 找到未被收录顶点中dist最小的顶点
int findMinDist(MGraph* g, int dist[], int collected[]) {
    int minV = -1;
    int minDist = MaxWeight;
    for (int v=0; v < g->vertexNum; v++) {
        if (!collected[v] && dist[v] < minDist) {
            // 未收录，且dist[v]更小
            minDist = dist[v];
            minV = v;
        }
    }
    // 返回找到的顶点，若没找到，返回的就是初始值-1
    return minV;
}

/**
 * 单源最短路径算法
 * g 图
 * costMatrix 花费权重
 * path 计算得到的路径
 * dist 计算得到的距离
 * cost 计算得到的花费
 * s 开始节点
*/
int dijkstra(MGraph* g, WeightType** costMatrix, int path[], int dist[], int cost[], int s) {
    int* collected = (int*) calloc(g->vertexNum, sizeof(int));
    // 初始化
    for (int v=0; v < g->vertexNum; v++) {
        dist[v] = g->g[s][v];
        cost[v] = costMatrix[s][v];
        if (dist[v] < MaxWeight) {
            path[v] = s;
        } else {
            path[v] = Connectionless;
        }
        collected[v] = 0;
    }
    // 先把起点收入
    collected[s] = 1;
    dist[s] = 0;

    for (;;) {
        // 找到未被收录顶点中dist最小的顶点
        int v = findMinDist(g, dist, collected);
        if (v == -1){
            break;
        }
        collected[v] = 1; // 收录v
        for (int w=0; w < g->vertexNum; w++) {
            if (g->g[v][w] < 0) {
                // 有负边，算法不支持，退出
                free(collected);
                return 0;
            }
            // 对 v 的每个未收录的邻接点 w
            if (!collected[w] && g->g[v][w] < MaxWeight) {
                if (dist[v] + g->g[v][w] < dist[w]) {
                    // 找到最短路径
                    dist[w] = dist[v] + g->g[v][w];
                    cost[w] = cost[v] + costMatrix[v][w];
                    path[w] = v;
                } else if (dist[v] + g->g[v][w] == dist[w] && cost[v] + costMatrix[v][w] < cost[w]) {
                    // 路径相等，花费不同
                    cost[w] = cost[v] + costMatrix[v][w];
                    path[w] = v;
                }
            }
        }
    }
    free(collected);
    return 1;
}

#endif
